#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e6 + 5;
const int MOD = 19940417;

int n, k;
struct Node {
  ll x, y;
} a[N];
bool operator<(Node a, Node b) { return a.x < b.x; }
bool operator==(Node a, Node b) { return a.x == b.x && a.y == b.y; }
ll f[N][2], mx;

ll fastpow(ll b, ll p) {
  ll res = 1;
  while (p) {
    if (p & 1) res = res * b % MOD;
    b = b * b % MOD;
    p >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  rep(i, 1, k) cin >> a[i].x >> a[i].y;
  a[++k] = Node{0, 0};
  a[++k] = Node{n, 0};
  sort(a + 1, a + k + 1);
  k = unique(a + 1, a + k + 1) - a - 1;
  f[1][1] = 1;
  rep(i, 2, k) {
    ll d = a[i].x - a[i].y - a[i - 1].x - a[i - 1].y;
    d >>= 1;
    if (a[i].x - a[i - 1].x == a[i].y - a[i - 1].y) {  // inc
      if (!a[i - 1].y)
        f[i][0] = f[i - 1][1];
      else
        f[i][0] = f[i - 1][0];
    } else if (a[i].x - a[i - 1].x == a[i - 1].y - a[i].y) {
      f[i][1] = (f[i - 1][0] + f[i - 1][1]) % MOD;
    } else if (d < 0) {
      f[i][1] = f[i - 1][0];
    } else if (d == 0) {
      f[i][1] = f[i - 1][0];
      f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
    } else {
      ll t = fastpow(2, d - 1) * (2 * f[i - 1][0] + f[i - 1][1]) % MOD;
      if (a[i].y) f[i][0] = t;
      f[i][1] = t;
    }
    if ((f[i][1] || !a[i].y) && (f[i - 1][0] || !a[i - 1].y))
      mx = max(mx, a[i].x - a[i - 1].x + a[i].y + a[i - 1].y);
  }
  cout << f[k][1] << ' ' << mx / 2;
  return 0;
}